package demo2;

/**
 * 路径问题
 *      地下城游戏 174
 */
public class test6 {
    public int calculateMinimumHP(int[][] dungeon) {
        // 创建dp表
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];
        // 初始化
        for(int i=0;i<=m;i++){
          dp[i][n] = Integer.MAX_VALUE;
        }
        for(int j=0;j<=n;j++){
            dp[m][j] = Integer.MAX_VALUE;
        }
        dp[m][n-1] = dp[m-1][n] = 1;
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                dp[i][j] = Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
                dp[i][j] = Math.max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }
}
